package com.ming.learn.from.carl.binary.tree;

import com.ming.commons.utils.TreeNode;
import com.sun.jmx.remote.internal.ArrayQueue;

import java.util.Stack;

//226.翻转二叉树
public class Of20210306LeetCode226 {
    /*
    翻转一棵二叉树。
     */
    public static void main(String[] args) {
        System.out.println(invertTree3(new TreeNode(1, new TreeNode(2, new TreeNode(4)
                , new TreeNode(5)), new TreeNode(3, new TreeNode(6), new TreeNode(7)))));
    }
    /*
    「注意只要把每一个节点的左右孩子翻转一下，就可以达到整体翻转的效果」
    「这道题目使用前序遍历和后序遍历都可以，唯独中序遍历不行，因为中序遍历会把某些节点的左右孩子翻转了两次！建议拿纸画一画，就理解了」
    「依然可以的！只要把每一个节点的左右孩子翻转一下的遍历方式都是可以的！」
     */

    /*
    递归法
     */
    private static TreeNode invertTree(TreeNode root) {
        if (root == null) return root;
        TreeNode node;
        node = root.left;
        root.left = root.right;
        root.right = node;
        invertTree(root.left);
        invertTree(root.right);
        return root;
    }

    /*
    迭代法(统一法)
     */
    private static TreeNode invertTree2(TreeNode root) {
        Stack<TreeNode> stack = new Stack<>();
        if (root != null) stack.push(root);
        while (!stack.isEmpty()) {
            TreeNode node = stack.pop();
            if (node != null) {
                if (node.right != null) stack.push(node.right);
                if (node.left != null) stack.push(node.left);
                stack.push(node);
                stack.push(null);
            } else {
                node = stack.pop();

                TreeNode treeNode;
                treeNode = node.left;
                node.left = node.right;
                node.right = treeNode;
            }
        }
        return root;
    }

    /*
    广度优先遍历
     */
    private static TreeNode invertTree3(TreeNode root) {
        ArrayQueue<TreeNode> que = new ArrayQueue<>(10);
        if (root != null) que.add(root);
        while (!que.isEmpty()) {
            for (int i = 0; i < que.size(); i++) {
                TreeNode node = que.remove(0);

                TreeNode treeNode;
                treeNode = node.left;
                node.left = node.right;
                node.right = treeNode;

                if (node.left != null) que.add(node.left);
                if (node.right != null) que.add(node.right);
            }
        }
        return root;
    }
}
